#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 삽입정렬 : 제자리를 찾을때까지 한칸씩 밀어서 자리를 마련
 * 오름차순(작은수 - 큰수)
 */


// 비교 함수 : a가 크면 1, b가 크면 -1, 같으면 0
int cmp(int a, int b) {
    if (a == b) {
        return 0;
    }
    else if (a > b) {
        return 1;
    }
    else {
        return -1;
    }
}

int insertion_sort(int* array, int count, int order, int(*pcmp)(int,int)) {
    int i = 0, j = 0;
    int value;

    for (i = 1; i < count; i++) {
        j = i - 1;
        value = array[i];
        while( j >= 0 && (order ? (pcmp(array[j],value)>0) : (pcmp(array[j],value)<0)) ) {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j + 1] = value;
    }
}

#define DATA_COUNT 11
int main(int argc,char** argv) {
    int i;
    int a[DATA_COUNT] = { 1, 8, 9, 7, 4, 3, 6, 5, 2, 10, 10};    
    insertion_sort(a, DATA_COUNT, 0, cmp);
    
    for (i = 0; i < DATA_COUNT; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
